#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int er(vector<int>& table, int num)
    {
        int left = 0, right = table.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (table[mid] < num) left = mid + 1;
            else if (table[mid] > num) right = mid;
            else return mid;
        }
        return left;
    }
    int lengthOfLIS(vector<int>& nums) {
        vector<int> table;
        table.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            int n = er(table, nums[i]);
            if (n == table.size() - 1 && nums[i] > table[n]) table.push_back(nums[i]);
            else table[n] = nums[i];
        }
        return table.size();
    }
};